//THIS IS THE CODE TO IMPLEMENT LINKED LISTS
#include<stdio.h>
#include<stdlib.h>
struct node
{
int val;
struct node *next;
};
//to create the linked list
struct node *insert(struct node *list,int num)
{
struct node *temp;

temp=malloc(sizeof(struct node));
temp->val=num;
temp->next=list;

return temp;
}
//to insert a node
struct node *ins(struct node *list,int x, int p1,int n)
{
int i=1;
struct node *p;

struct node *t;
t=malloc(sizeof(struct node));

p=list;
if(p1==1)
{
t->val=x;
t->next=p;
list=t;
}
else if(p1>n)
printf("invalid position");
else{
while(i!=p1-1)
{

p=p->next;
i++;
}

t->val=x;
t->next=p->next;
p->next=t;}
return list;
}
//to delete a node
struct node *delete(struct node *list,int x)
{
int f=0;
struct node *p=NULL;
struct node *c;
c=malloc(sizeof(struct node));
c=list;
while(c!=NULL)
{
if(c->val==x){
f=1;
break;}
p=c;
c=c->next;
}
if(f==1){
if(p== NULL)
list=list->next;
else
{

p->next=c->next;
free(c);

}}
else
printf("invalid element\n");
return list;
}

//to append a node
struct node *append(struct node *list,int x)
{

struct node *temp;
struct node *p;

p=list;
temp=malloc(sizeof(struct node));
temp->val=x;
temp->next=NULL;
while((p->next)!=NULL)
{p=p->next;}

p->next=temp;
return list;
}
//to reverse the list
struct node *reverse(struct node *list)
{

struct node *p=NULL, *c ,*r=NULL;
p=malloc(sizeof(struct node));
c=malloc(sizeof(struct node));



c->val=list->val;
c->next=NULL;
p=c;
list=list->next;
while(list!=NULL)
{
r=malloc(sizeof(struct node));
r->val=list->val;
r->next=p;
p=r;
list=list->next;

}
return r;

}
//to count the occurences
void count(struct node *list,int x)
{

int c=0,f=0;

while(list!=NULL)
{
if(list->val == x){
f=1;
c++;}list=list->next;
}
if(f==0)
printf("not found\n");
else
printf("%d\n", c);
}
//to find the index of a node
void index_num(struct node *list,int x)
{


int i=0,f=0;

while(list!=NULL)
{
if(list->val == x)
{f=1;
break;}
i++;
list=list->next;
}
if(f==1)
printf("index is%d\n",i);
else
printf("no. not found\n");
}
//to extend the list
struct node *extend_list(struct node *list, struct node *list1)
{
struct node *p;
p=list;
while((p->next)!=NULL)
{
p=p->next;
}
p->next=list1;
return list;
}
//to pop out an element of a position
struct node *pop_element(struct node *list,int n,int d)
{
int i=1,p1;
struct node *p=NULL;
struct node *c;
c=malloc(sizeof(struct node));
c=list;
while(i!=d && c!=NULL)
{
p=c;
c=c->next;
i++;
}
if(i==d)
{
if(p== NULL){
printf("deleted element %d\n", list->val);
list=list->next;}
else
{
if(c!=NULL)
{
p->next=c->next;
printf("deleted element %d\n", c->val);
free(c);
}
}
}
else
printf("invalid index");
return list;
}
//to search for an element
void search(struct node *list, int n, int x)
{
int i=1,f=0;
while((list->next)!=NULL)
{
if(list->val==x)
{
printf("element found at position %d\n", i);
f=1;
break;}
i++;
list=list->next;}
if(f==0)
printf("not found\n");
}
//to sort the list
struct node *sort_list(struct node *list,int n) 
{
struct node *p1,*p2,*p3,*p4;
struct node *p5=NULL;
int i,j;
while(p5!=list->next) 
{
p1=list;
p3=p1;
p2 =p1->next;
while(p1 != p5)
{
if(p1->val > p2->val) 
{
if(p1->val == list->val) 
{
p4 = p2 -> next;
p2->next = p1;
p1->next = p4;
list= p2;
p3 = p2;
} 
else {
p4 = p2->next;
p2->next = p1;
p1->next = p4;
p3->next = p2;
p3 = p2;
}}
else {
p3 = p1;
p1 = p1->next;
}
p2 = p1->next;
if(p2 ==p5)
p5=p1;
}
} 
return list;
}
//to display the list
void display(struct node *list)
{
while(list!=NULL)
{
printf("%d", list->val);
list=list->next;
}
printf("\n");
}

//main function
void main()
{

struct node *first=NULL;
struct node *first1=NULL;
struct node *d;
d=malloc(sizeof(struct node));
int n,i,x,p,choice,l,l1,n1,c=1,t;
printf("enter length: ");
scanf("%d", &l);
printf("enter elements: ");
for(i=0;i<l;i++)
{
scanf("%d",&n);
first=insert(first,n);

}
while(c==1)
{
printf("enter choice:\n 1.append\n 2.reverse\n 3. delete\n 4.insert\n 5.count\n 6.index\n 7.extend\n 8.sort\n 9.pop\n 10.search\n ");
scanf("%d", &choice);
switch(choice)
{
case 1:

printf("enter element to append: ");
scanf("%d",&x);
first=append(first,x);
display(first);
break;
case 2:

first=reverse(first);

printf("reversed\n");
display(first);
break;
case 3:
printf("enter element to delete: ");
scanf("%d", &x);
first=delete(first,x);
display(first);
break;
case 4:

printf("enter number to insert: ");
scanf("%d", &x);
printf("enter position to insert: ");
scanf("%d", &p);
first=ins(first,x,p,n);

display(first);


break;

case 5:
printf("enter no. t count: ");
scanf("%d", &x);

count(first,x);
break;

case 6:
printf("enter no. to find index: ");
scanf("%d", &x);
index_num(first, x);
break;

case 7:

printf("enter length: ");
scanf("%d", &l1);
printf("enter elements: ");
for(i=0;i<l1;i++)
{
scanf("%d",&n1);
first1=insert(first1,n1);
}

first=extend_list(first,first1);
display(first);
break;
case 8:

first=sort_list(first,l);

display(first);
break;
case 9:
printf("enter position to delete element: ");
scanf("%d", &x);
first=pop_element(first,n,x);

printf("\n");
display(first);
break;
case  10:
printf("enter element to be searched: ");
scanf("%d", &x);
search(first,n,x);
break;
default:
printf("error\n");
}
printf("u wanna continue? yes:1 no:0\n");
scanf("%d", &t);
c=t;
}


}

